In many medical imaging applications, such as image-guided radiotherapy, adaptive radiation therapy, magnetic resonance imaging (MRI), and computer axial tomography (CAT), deformable image registration (DIR) is a challenge for images of organs and soft tissue. Discontinuous deformations occur at organ and tissue boundaries. For example, in the case of respiratory motion, a discontinuous deformation occurs along the boundary between the lungs and surrounding tissue.
Prior art methods for DIR registration generally assume that the underlying deformations are inherently smooth. Therefore, those methods cannot account for discontinuities. To circumvent the discontinuity problem, one method segments each organ and perform registration on each organ independently and separately. However, that requires accurate segmentation as a preprocessing step, which is not an easy task for medical images, particularly if the organs and tissue are intertwined.
Discontinuities in the underlying deformations can be preserved by using a discrete optimization approach, where deformation vectors are represented with a set of labeled vectors, see e.g., Seo and van Baar, “Deformable registration with discontinuity preservation using multi-scale MRF,” Proceedings of Workshop on Image-Guided Adaptive Radiation Therapy, 2014.
A drawback of formulating the deformable registration as a labeling problem, is that many labels are required to accurately approximate the underlying deformations. Thus, discontinuity preserving approaches require longer optimization time, compared to, for example, methods that use dense image registration such as (diffeomorphic) demons, or B-splines.
DIR can be classified into continuous and discrete methods. Continuous methods assume a smooth underlying deformation field, while discrete methods explicitly handle discontinuities in the deformation field. Determining accurate deformation vectors requires a large label set, which results in increased computational time and memory.
Parallelization of graph cuts can improve the computational speed of the DIR. In a parallel approach, parts of the solution are computed in parallel and then combined into a single solution.
Parallelized graph cuts have been applied in a region-based push-relabel approach, see Boykov et al., “An experimental comparison of min-cut/max-flow algorithms for energy minimization in vision,” IEEE Pattern Analysis and Machine Intelligence 26(9), September, 2004. By redefining relabeling heuristics on the regions, rather than globally, they achieve both locality and parallelism. The boundary nodes of a region are considered constant, to maintain a global consistency of the graph.
Another method uses a two phase parallel scheme, see Liu et al., “Parallel graph-cuts by adaptive bottom-up merging,” IEEE Computer Vision and Pattern Recognition (CVPR), June, 2010. In a first phase a the graph is partitioned into subgraphs, and augmented paths for the subgraphs are determined in parallel. In a second phase, the subgraphs are adaptively fused by restoring capacities between boundary nodes of two blocks. This merging yields longer augmented paths, and eventually finding a global optimum.
Another method uses splits the graph, with some overlap, and subsequently distributes across multiple computers, see Strandmark et al., “Parallel and distributed graph cuts by dual decomposition, IEEE Computer Vision and Pattern Recognition (CVPR), June, 2010. That method formulates a dual decomposition to solve a binary labeling problem with consistent labels for the nodes in overlapping region.